As technology nodes of semiconductor manufacturing decrease, multiple patterning techniques (MPT) are used to form features on a semiconductor wafer in closer proximity than is possible with a single patterning process. MPT use multiple masks in order to form the features on the semiconductor wafer. Coloring refers to the assignment of a particular feature to a corresponding mask.
A conflict graph is used to assist in the coloring process. The conflict graph includes nodes, each node corresponding to one of the features, and links connecting nodes. Links connect nodes which have a separation less than a minimum distance for forming nodes on a same mask. Nodes connected by a link are assigned to different masks, i.e., have different colors. Many conflict graphs include multiple coloring solutions. The multiple coloring solutions are called a solution space.
Rule-based approaches identify a single solution within the solution space. Rule-based approaches assign colors to different nodes based on defined rules. Once a rule-based approach identifies a solution which satisfies each of the rules, the rule-based approach stops. Heuristic approaches are able to identify multiple solutions within the solution space. However, the heuristic approach requires more processing time than the rule-based approaches.